1. Field of the Invention
The present invention relates to a decoding device for decoding a data stream, and more particularly to a decoding device for decoding a data stream containing Huffman-encoded data.
2. Description of the Related Art
Recently, decoding devices for decoding a Huffman-encoded bit stream (data stream) have been widely developed. Decoding methods used in such decoding devices are generally categorized into two types. One type focuses on saving memory. The other type focuses on increasing decoding speed. An encoding method will be initially described before describing such decoding methods.
FIG. 11 shows an example of a Huffman encoding book 1100 used in Huffman encoding. The left column 1101 of the Huffman encoding book 1100 indicates input values to be Huffman-encoded. In the example shown in FIG. 11, the input values range from 0 through 63. The middle column 1102 of the Huffman encoding book 1100 indicates Huffman codes corresponding to the respective input values. The right column 1103 of the Huffman encoding book 1100 indicates a code length corresponding to the respective Huffman codes. In Huffman encoding, the higher the frequency of occurrence of an input value, the shorter the Huffman code which is assigned to the input value. Conversely, the lower the frequency of occurrence of an input value, the longer the Huffman code which is assigned to the input value.
For example, the first row 1104 of the Huffman encoding book 1100 indicates that a Huffman code (01110) is assigned to an input value 0, and the code length of the Huffman code is 5 bits. An encoding device receives and encodes an input value 0 and outputs the resulting Huffman code (01110). The encoding device does not need to output information indicating the code length of the Huffman code along with the Huffman code. This is because any code which has the same digit sequence beginning from the leftmost digit of a Huffman code (01110) but is shorter than the Huffman code (01110) cannot be included in the Huffman encoding book 1100. All the other Huffman codes which have a code length of five or more do not contain the Huffman code (01110) as a digit sequence beginning with the leftmost digit of the other Huffman codes. Accordingly, when a decoding device decodes the Huffman code (01110), the decoding device does not need information specifically indicating that the code length of the Huffman code (01110) is 5 bits. Thus, a Huffman code (01110) itself can include information indicating which input value (0) the Huffman code corresponds to and information indicating the code length (5) of the Huffman code.
For that reason, Huffman codes can be generated in a contiguous way to produce a bit stream which is then output from the encoding device.
Hereinafter, a conventional decoding method focusing on saving memory will be described. FIG. 12 shows a decoding table 1200 used for decoding data encoded with the Huffman encoding book 1100 shown in FIG. 11. The decoding table 1200 is obtained by rearranging the rows of the Huffman encoding book 1100 shown in FIG. 11 in order of the code length of the Huffman code from the shortest. The left column 1102A of the decoding table 1200 indicates Huffman codes. The middle column 1103A indicates the code length of the Huffman codes. The right column 1201 indicates the results of decoding the Huffman codes. As is seen from FIG. 12, a Huffman code having a code length of three bits (000) on the first row 1202 is the shortest Huffman code. The result from decoding the Huffman code (000) is "9" which corresponds to the tenth row 1105 (input value "9") of the Huffman encoding book 1100 shown in FIG. 11.
As is also seen from FIG. 12, a Huffman code (1111111111) with 10 bits on the lowest row 1203 is one of the longest Huffman codes. The result from decoding the Huffman code (1111111111) is "63" which corresponds to the 64th row 1106 (input value "63") of the Huffman encoding book 1100 shown in FIG. 11.
Huffman decoding in a decoding device using the decoding table 1200 will be described below.
The first row 1202 (the uppermost row) of the decoding table 1200 indicates that the code length is three. Based on this code length, a first three bits are read out of a bit stream. The decoding device determines whether the first three bits of data of the bit stream match the Huffman code (000) on the first row 1202.
If the matching is successful (i.e., a match is found), the decoding device outputs "9" as the result of the decoding, and shifts a reading position in the bit stream by three bits. One Huffman-decoding operation is thus finished.
If the matching is not successful, a next row 1204 of the decoding table 1200 is considered. The second row 1204 has a code length of four. Accordingly, an additional one bit (1=4-3) next to the three bits which already have been read out is read out of the bit stream.
It is then determined whether the four bit data thus read matches a Huffman code (0010) on the second row 1204.
If the matching is successful, "17" is output as the result of the decoding. The reading position of the bit stream is shifted by one bit. One Huffman-decoding operation is thus finished.
If the matching is not successful, a next row 1205 of the decoding table 1200 is looked up. The third row 1205 has a code length of four. Accordingly, no new bit is read out of the bit stream. It is then determined whether the four bit data thus currently read matches the Huffman code (0011) on the third row 1205.
In this way, the matching procedure is repeated until data which is sequentially read out of the bit stream matches any of the Huffman codes contained in the decoding table 1200. When the decoding device finds a row having a Huffman code matching the data, the decoding device outputs the value on the right column of the row as the result of the decoding operation.
The decoding table used in the above-described decoding method is very small in size. This is because such a decoding table only needs the same number of rows as that of input values (0 to 63). In the decoding method, however, the decoding table is accessed many times in the matching procedure until a matching Huffman code is found. This requires considerable processing time.
Next, a conventional decoding method focusing on increasing decoding speed will be described below.
FIG. 13 shows a decoding table 1300 used in decoding data which has been encoded using the Huffman encoding book 1100 shown in FIG. 11. An example of the decoding method represented in FIG. 13 uses addresses having a ten-bit width. The bit width (10 bits) of the addresses corresponds to the maximum code length (10 bits) of the Huffman codes in the Huffman encoding book 1100 shown in FIG. 11.
A decoding device reads 10-bit data out of a bit stream and accesses the decoding table 1300 using the 10-bit data as an address. In the decoding table 1300, an area 1301 including addresses (0000000000) through (0001111111) describes that a code length is three and the result of the decoding operation is "9". The 10-bit data in which the first three bits are a Huffman code (000) is necessarily among the addresses (0000000000) through (0001111111). The Huffman code (000) corresponds to the value "9". In this case, the decoding device outputs "9" as the result of the decoding corresponding to the first three bits (000) based on the decoding table 1300 shown in FIG. 13. The area 1301 indicates that the code length is three. Accordingly, the decoding device shifts a reading position by three bits and reads 10-bit data from the reading position. The decoding table 1300 shown in FIG. 13 is accessed using the 10-bit data as an access. Thus, the next Huffman decoding operation is performed.
The above-described decoding method can achieve high speed. Each Huffman decoding operation is finished by one access to the decoding table. However, the decoding method focusing on increasing decoding speed requires a vast-size decoding table compared with the decoding method focusing on saving memory.
As described above, the decoding method focusing on saving memory requires much processing time. The decoding method focusing on increasing decoding speed requires a large decoding table and therefore cannot achieve memory savings.
For example, recent audio decoding devices in conformity with the MPEG2-AAC standard need to decode Huffman codes which are encoded using twelve different Huffman code books. In this case, if all he Huffman encoding books are provided with decoding tables for high-speed decoding as shown in FIG. 13, a vast amount of memory is required. On the other hand, the MPEG2-AAC standard requires multiple channels and hi-fi audio with a high sampling rate. The use of decoding table for saving memory as shown in FIG. 12 requires vast processing performance.